package sort;

import java.util.Stack;

/**
 * 快速排序迭代实现
 * 注意：
 *      入栈是先左后右边，那么出栈就是先右后左*/
public class QuickSortIteration {
    public static void quickSort(int[] array) {
        int start = 0;
        int end = array.length - 1;
        Stack<Integer> stack = new Stack<>();
        stack.push(start);
        stack.push(end);
        while (!stack.empty()) {

            int right = stack.pop();
            int left = stack.pop();

            int pivot = partition(array,left,right);
            if(pivot-1 > left) {
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot+1 < right) {
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }

    //按照基准值分割 Hoare法
    private static int partition(int[] array, int left, int right) {
        //默认基准值为left
        int target = array[left];
        int record = left;
        while (left < right) {
            while (left < right && array[right] >= target) {
                right--;
            }
            while (left < right && array[left] <= target) {
                left++;
            }
            swap(array, left, right);
        }
        swap(array, record, left);
        return left;
    }


    //交换
    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}
